package algotithm.leetcode.stack.test946;

import java.util.Stack;

/**
 * @author zhouyanxiang
 * @Date 2021-03-2021/3/1-21:39
 * @URL https://leetcode-cn.com/problems/validate-stack-sequences/
 * @Title 946. 验证栈序列
 */
class Solution {

    public static void main(String[] args) {
        int[] pushed = {1,2,3,4,5};
        int[] poped = {4,5,3,2,1};
        Solution solution = new Solution();
        boolean flag = solution.validateStackSequences(pushed,poped);
        System.out.println(flag);
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int n = pushed.length;
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int x : pushed) {
            stack.push(x);
            while (!stack.isEmpty() && j < n && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return j == n;
    }
}


